#include <iostream>

const int MAXN = 100001;
int father[MAXN];
int size[MAXN];
int n;

void Build(){
    for(int i=0; i<=n;i++){
        //每个元素都指向自己
        father[i]=i;
        //每个集合的大小都是1
        size[i]=1;
    }
}

//i号节点往上一直找，直到找到根节点
int Find(int i){
    while(i != father[i]){
        i = father[i];
    }

    return i;
}


//判断x,y是不是同一个集合
bool IsSameSet(int x, int y){
    return Find(x) == Find(y);
}


//合并两个集合
void Union(int x,int y){
    int fx = Find(x);
    int fy = Find(y);

    if (fx != fy){
        //谁小谁挂下面
        if (size[fx] > size[fy]){
            //吸收大小
            size[fx] += size[fy];
            //fy挂到fx下面
            father[fy] = fx;
        }else{
            size[fy] += size[fx];
            //fx挂到fy下面
            father[fx] = fy;
        }
    }
}

/**
 * 
 * 并查集基本模板
 */
int main(){
    n = 6;
    Build();

    Union(1,2);
    Union(3,4);

    std::cout << IsSameSet(1,3);

    Union(1,3);

    Union(5,6);

    Union(1,5);

    return 0;
}